package com.sali.DP;

/**
 * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */
public class LeetCode_188 {

    public int maxProfit(int k, int[] prices) {
        int[][][] dp = new int[prices.length + 1][k + 1][2];
        for (int nk = 0; nk < k + 1; nk++) {
            dp[0][nk][0] = 0;
            dp[0][nk][1] = Integer.MIN_VALUE;
        }

        for (int nd = 1; nd < prices.length + 1; nd++) {
            for (int nk = 1; nk < k + 1; nk++) {
                dp[nd][nk][0] = Math.max(dp[nd - 1][nk][0], dp[nd - 1][nk][1] + prices[nd - 1]);
                dp[nd][nk][1] = Math.max(dp[nd - 1][nk][1], dp[nd - 1][nk - 1][0] - prices[nd - 1]);
            }
        }

        return dp[prices.length][k][0];
    }

}
